import re
from block_table import *

class BasicBlock():
	def __init__(self,name=None):
		self.locs = []

	def addLoc(self,index,loc):
		self.locs.append({"index":index,
				  "btname":loc['btname'],
				  "loc":loc['loc']})

	def reverseLocs(self):
		reversedLocs = self.locs[:]
		reversedLocs.reverse()
		return reversedLocs

	def getLocs(self):
		return self.locs

class BasicBlocks():
	def __init__(self,locs,blockTable):
		self.locs = locs
		self.basicBlocks=[]
		self.targets = []
		self.leaders = []
		self.blockTable = blockTable
		
	def setTargets(self):
		for line in self.locs:
			if "GOTO" in line['loc']:
				ifRe = re.compile("(^IF )(.*)( GOTO )(.*)")
				gotoRe = re.compile("(^GOTO )(.*)")
				ifReRes = ifRe.match(line['loc'])
				gotoReRes = gotoRe.match(line['loc'])

				if(ifReRes != None):
					newTarget = ifReRes.group(4)
				else:
					newTarget = gotoReRes.group(2)

				self.addTarget(newTarget.replace(":",""))


	def setLeaders(self):
		defFunctionRe = re.compile("(^FUNCTION_)(.*)")
		i = 0

		for line in self.locs:
			if i == 0:
				# first instruction is a leader
				self.leaders.append(i)
			elif "GOTO" in line['loc']:
				# jump instruction
				ifRe = re.compile("(^IF )(.*)( GOTO )(.*)")
				gotoRe = re.compile("(^GOTO )(.*)")
				ifReRes = ifRe.match(line['loc'])
				gotoReRes = gotoRe.match(line['loc'])

				if(ifReRes != None):
					target = ifReRes.group(4)
				else:
					target = gotoReRes.group(2)

				# target for jump is a leader
				self.addTarget(target)
			
				if i < len(self.locs) -1:
					# i is not last line index
					self.addLeader(i+1)
					# next Instruction after loop is a leader


			elif ":" in line['loc']:
				line = line['loc'].replace(':','')

				if line in self.targets:
					#target instruction, then leader
					self.addLeader(i)

				
			#	elif defFunctionRe.search(line) != None:
			#		#function start is always a leader
			#		print "///////////////////////////////"
			#		print "function start is always a leader"
			#		self.addLeader(i)
			i += 1

		self.leaders.sort()

	def addTarget(self,target):
		if target not in self.targets:
			#print "*******************************************"
			#print "ADD TARGET:",target
			#print "*******************************************"
			self.targets.append(target)

	def addLeader(self,leader):
		if leader not in self.leaders:
			self.leaders.append(leader)

	def orderMainLocs(self):
		'''main locs could be dispersed among the functions so before main
		   block generation, we must order main locs'''
		stNamesQueue = []
		mainLocs = []
		functionLocs = []

		btEntry = self.blockTable.getMainBlockTableEntry()
		currentStName = btEntry.getName()
		mainBtEntryName = btEntry.getName()
		stNamesQueue.append(currentStName) # push main st name

		defFunctionRe = re.compile("(^FUNCTION_)(.*)(:)")
		endFunctionRe = re.compile("(^END_FUNCTION_)(.*)(:)")


		for i in range(len(self.locs)):
			defFunction = defFunctionRe.search(self.locs[i])
			endFunction = endFunctionRe.search(self.locs[i])

			if (defFunction != None):
				# begining of a function
				
				functionName = defFunction.group(2)
				stNamesQueue.append(functionName)
				currentStName = functionName

			elif (endFunction != None):
				#ending function
				stNamesQueue.pop()
				currentStName = stNamesQueue[-1]

			loc = self.locs[i]

			if (currentStName == mainBtEntryName and "END_FUNCTION" not in loc):
				mainLocs.append({"btname":mainBtEntryName,"loc":loc})
			else:
				functionLocs.append({"btname":currentStName,"loc":loc})


		self.locs = functionLocs + mainLocs

	def genBasicBlocks(self):
		self.orderMainLocs()
		self.setTargets()
		self.setLeaders()
		#DEBUG
		#print "----------LEADERS--------------"
		#for leader in self.leaders:
		#	print "leader:",leader
		#for target in self.targets:
		#	print "target:",target
		#print "----------------------------"
		#FINDEBUG

		for i in range(len(self.leaders)):
			basicBlock = BasicBlock()

			if i < len(self.leaders ) -1:
				
				for j in range(self.leaders[i],self.leaders[i+1]):
					basicBlock.addLoc(j,self.locs[j])
			else:
				for j in range(self.leaders[i],len(self.locs)):
					basicBlock.addLoc(j,self.locs[j])

			self.basicBlocks.append(basicBlock)


		self.setLiveAndNextUse()

	def setLiveAndNextUse(self):
		for basicBlock in self.basicBlocks:
			reversedLocs = basicBlock.reverseLocs()

			for loc in reversedLocs:
				btEntry = self.blockTable.getBlockTableEntry(loc['btname'])
				if ('if' in loc['loc']):
					#read access
					terms = loc['loc'].split()

				elif (":=" in loc['loc']):
					#assign
					terms = loc['loc'].split()
					if (len(terms)==3):
						# x = y : copy op
						btEntry.setNoLive(terms[0])
						btEntry.setNoNextUse(terms[0])

						btEntry.setLive(terms[2])
						btEntry.setNextUse(terms[2],loc['index'])
						#print loc['loc']
						#print self.blockTable.printAll()
					elif (len(terms)==5):
						# x = y op z
						btEntry.setNoLive(terms[0])
						btEntry.setNoNextUse(terms[0])

						btEntry.setLive(terms[2])
						btEntry.setNextUse(terms[2],loc['index'])
						btEntry.setLive(terms[4])
						btEntry.setNextUse(terms[4],loc['index'])
					else:
						#TODO check this 
						continue
	def getBasicBlocks(self):
		return self.basicBlocks
